# 27/100 链表-合并两个有序链表
# leetcode第21题: https://leetcode.cn/problems/linked-list-cycle-ii/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/18
from typing import Optional
from leetcode import test
from leetcode.bds import ListNode
from leetcode.bds import ListConvert


def mergeTwoLists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    """我的方法"""
    if not list1 and not list2:
        return None
    if not list1:
        return list2
    if not list2:
        return list1

    if list1.val <= list2.val:
        head, list1 = ListNode(list1.val), list1.next
    else:
        head, list2 = ListNode(list2.val), list2.next
    curr = head
    while list1 or list2:
        if list1 and list2:
            if list1.val <= list2.val:
                curr.next = ListNode(list1.val)
                list1, curr = list1.next, curr.next
            else:
                curr.next = ListNode(list2.val)
                list2, curr = list2.next, curr.next
        elif list1:
            curr.next = ListNode(list1.val)
            list1, curr = list1.next, curr.next
        else:
            curr.next = ListNode(list2.val)
            list2, curr = list2.next, curr.next

    return ListConvert.link_to_list(head)


def mergeTwoLists_opt(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    """优化"""
    if not list1 and not list2:
        return None
    if not list1:
        return list2
    if not list2:
        return list1

    head = ListNode(-1)
    curr = head
    while list1 and list2:
        if list1.val <= list2.val:
            curr.next = list1
            list1 = list1.next
        else:
            curr.next = list2
            list2 = list2.next
        curr = curr.next
    curr.next = list1 if list1 else list2
    return ListConvert.link_to_list(head.next)


if __name__ == '__main__':
    l1, l2 = ListConvert.list_to_link([1, 2, 4]), ListConvert.list_to_link([1, 3, 4])
    l3 = [1, 1, 2, 3, 4, 4]
    l4, l5 = ListConvert.list_to_link([1, 2, 4, 5, 6]), ListConvert.list_to_link([1, 3, 4])
    l6 = [1, 1, 2, 3, 4, 4, 5, 6]
    inp = [{"list1": l1, "list2": l2}, {"list1": l4, "list2": l5}]
    out = [l3, l6]
    test.test_function(mergeTwoLists, inp, out)
    test.test_function(mergeTwoLists_opt, inp, out)
